class Solution {
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& e) {
        int m=maze.size(),n=maze[0].size();
        bool vis[m][n];
        memset(vis,0,sizeof(vis));

        queue<pair<int,int>> q;
        q.push({e[0],e[1]});
        vis[e[0]][e[1]]=true;

        int step=0;
        while(q.size())
        {
            step++;
            int sz=q.size();
            for(int i=0;i<sz;i++)
            {
                auto [a,b]=q.front();q.pop();
                for(int j=0;j<4;j++)
                {
                    int x=a+dx[j],y=b+dy[j];
                    if(x>=0 && x<m 
                    && y>=0 && y<n 
                    && maze[x][y]=='.' && !vis[x][y])
                    {
                        if( x==0 ||x==m-1 || y==0 || y==n-1)return step;
                        q.push({x,y});
                        vis[x][y]=true;
                    }
                }
            }
        }
        return -1;
    }
};
